{"nbformat":4,"nbformat_minor":0,"metadata":{"colab":{"name":"chapter_advanced_graph_search.ipynb","provenance":[],"collapsed_sections":[],"toc_visible":true},"kernelspec":{"name":"python3","display_name":"Python 3.7.5 64-bit","metadata":{"interpreter":{"hash":"6f3fdc50dad01a00ee690c4e47d0eb586e790b94dbf60d4ad3bb7d6e393ce6fb"}}}},"cells":[{"cell_type":"markdown","metadata":{"id":"XFKuBveS1Cce"},"source":["* Cycle Detection : check the figure\n","* Topological Sort: keep the left figure\n","* Eulerian Circuit (optional)\n","\n","To do list\n","* Each section should have a fun application with better figure!!!\n","* the disjoint set can be improved using tree: https://www.hackerearth.com/practice/algorithms/graphs/minimum-spanning-tree/tutorial/\n","* Proof to dijkstra should be a practice of the proof of greedy algorithms\n","* Add more leetcode examples.\n","\n","Resources\n","* https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/14/Small14.pdf\n","https://homes.luddy.indiana.edu/achauhan/Teaching/B403/LectureNotes/09-mst.html"]},{"cell_type":"markdown","metadata":{"id":"auwghE4hWHSK"},"source":["### Cycle Detection"]},{"cell_type":"code","metadata":{"id":"6nYEnOCo3FOC","executionInfo":{"status":"ok","timestamp":1615934605072,"user_tz":420,"elapsed":542,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# initialization\n","class STATE:\n","  white = 0\n","  gray = 1\n","  black = 2"],"execution_count":1,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"dLTp6RWw2mYX"},"source":["#### Directed graph"]},{"cell_type":"code","metadata":{"id":"xPzr88zz2pw_","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934605693,"user_tz":420,"elapsed":1135,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"e6708800-f8e8-4444-f87b-478a38d3def6"},"source":["dcg = [[1], [2], [0, 4], [], [3], [6], []]"],"execution_count":61,"outputs":[]},{"cell_type":"code","metadata":{"id":"iq07bZAp29mi","executionInfo":{"status":"ok","timestamp":1615934605694,"user_tz":420,"elapsed":1135,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def hasCycleDirected(g, s, state):\n","  state[s] = STATE.gray # first be visited\n","  for v in g[s]:\n","    if state[v] == STATE.white:\n","      if hasCycleDirected(g, v, state):\n","        print(f'Cycle found at node {v}.')\n","        return True\n","    elif state[v] == STATE.gray: # aback edge\n","      print(f'Cycle starts at node {v}.')\n","      return True\n","    else:\n","        pass\n","    state[s] = STATE.black # mark it as complete\n","    return False"],"execution_count":75,"outputs":[]},{"cell_type":"code","metadata":{"id":"zbtKB8Rg3bWg","executionInfo":{"status":"ok","timestamp":1615934605694,"user_tz":420,"elapsed":1133,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def cycleDetectDirected(g):\n","  n = len(g)\n","  state = [STATE.white] * n\n","  for i in range(n):\n","    if state[i] == STATE.white:\n","      if hasCycleDirected(g, i, state):\n","        return True\n","  return False"],"execution_count":63,"outputs":[]},{"cell_type":"code","metadata":{"id":"q-0e10OJ4M5i","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934605695,"user_tz":420,"elapsed":1127,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"ac9579cb-4dfa-4c9c-ecec-475fe8e9e439"},"source":["cycleDetectDirected(dcg)"],"execution_count":64,"outputs":[{"output_type":"stream","name":"stdout","text":["Cycle starts at node 0.\nCycle found at node 2.\nCycle found at node 1.\n"]},{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{},"execution_count":64}]},{"cell_type":"code","execution_count":77,"metadata":{},"outputs":[],"source":["# run one with a forward edge, change (2, 0) to (0, 2)\n","dag = [[1, 2], [2], [4], [], [3], [6], []]\n"]},{"cell_type":"code","execution_count":78,"metadata":{},"outputs":[{"output_type":"execute_result","data":{"text/plain":["False"]},"metadata":{},"execution_count":78}],"source":["cycleDetectDirected(dag)"]},{"cell_type":"markdown","metadata":{"id":"GTx9ANEY562r"},"source":["#### Undirected Graph"]},{"cell_type":"code","metadata":{"id":"wE01rAq55-oF","executionInfo":{"status":"ok","timestamp":1615934605695,"user_tz":420,"elapsed":1126,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def hasCycleUndirected(g, s, p, visited):\n","  visited[s] = True\n","  for v in g[s]:\n","      if not visited[v]:\n","        if hasCycleUndirected(g, v, s, visited):\n","          print(f'Cycle found at node {v}.')\n","          return True\n","      else:\n","        if v != p: # both black and gray\n","          print(f'Cycle starts at node {v}.')\n","          print(visited[v])\n","          return True\n","\n","  return False"],"execution_count":98,"outputs":[]},{"cell_type":"code","metadata":{"id":"sA6dMqrE7MOC","executionInfo":{"status":"ok","timestamp":1615934605696,"user_tz":420,"elapsed":1125,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def cycleDetectUndirected(g):\n","  n = len(g)\n","  visited = [False] * n\n","  for i in range(n):\n","    if not visited[i]:\n","      if hasCycleUndirected(g, i, -1, visited):\n","        print(f'Cycle found at start node {i}.')\n","        return True\n","\n","  return False"],"execution_count":99,"outputs":[]},{"cell_type":"code","metadata":{"id":"aD-FizTB6WbB","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934605696,"user_tz":420,"elapsed":1118,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"6c8e950c-0cbb-4009-bbec-aa3e3e6530ff"},"source":["ucg=[[1, 2], [0, 2], [0, 4], [], [2, 3], [6], [5]]"],"execution_count":100,"outputs":[]},{"cell_type":"code","metadata":{"id":"30NtiTxy7TIq","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934605697,"user_tz":420,"elapsed":1112,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"6d1e5b2b-bc55-4a90-97f8-20405e8db6b1"},"source":["cycleDetectUndirected(ucg)"],"execution_count":101,"outputs":[{"output_type":"stream","name":"stdout","text":["Cycle starts at node 0.\nTrue\nCycle found at node 2.\nCycle found at node 1.\nCycle found at start node 0.\n"]},{"output_type":"execute_result","data":{"text/plain":["True"]},"metadata":{},"execution_count":101}]},{"cell_type":"code","execution_count":27,"metadata":{},"outputs":[{"output_type":"execute_result","data":{"text/plain":["False"]},"metadata":{},"execution_count":27}],"source":["# delete edge (0, 2)\n","uag = [[1], [0, 2], [4], [], [2, 3], [6], [5]]\n","cycleDetectUndirected(uag)"]},{"cell_type":"markdown","metadata":{"id":"WkpyVhW8WMN1"},"source":["# Topolgical Sort"]},{"cell_type":"code","metadata":{"id":"G1MfbU4eWPrA","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934605697,"user_tz":420,"elapsed":1106,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"f9c45bc2-48e6-4b6f-e899-105976220f66"},"source":["# Directed Acyclic Graph \n","dag = [[1], [2], [], [2, 4, 5], [], [6], []]\n","dag"],"execution_count":28,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[[1], [2], [], [2, 4, 5], [], [6], []]"]},"metadata":{},"execution_count":28}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"pmt__y5S0Wux","executionInfo":{"status":"ok","timestamp":1615934605698,"user_tz":420,"elapsed":1099,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"63caf923-44d6-4d12-87e3-230095a93776"},"source":["# Directed Cyclic Graph\n","dcg = [[1], [2], [3], [2, 4, 5], [], [6], []]\n","dcg"],"execution_count":29,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[[1], [2], [3], [2, 4, 5], [], [6], []]"]},"metadata":{},"execution_count":29}]},{"cell_type":"markdown","metadata":{"id":"TkdnK4fU1F4P"},"source":["## Kahn's algorithm"]},{"cell_type":"code","metadata":{"id":"FFG2ShFu1KPn","executionInfo":{"status":"ok","timestamp":1615934605908,"user_tz":420,"elapsed":1307,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["from collections import defaultdict\n","import heapq \n","def kahns_topo_sort(g):\n","  S = []\n","  V_S =[(0, node) for node in range(len(g))] # initialize node with 0 as in-degree\n","  indegrees = defaultdict(int)\n","  # Step 1: count the in-degree\n","  for u in range(len(g)):\n","    indegrees[u] = 0\n","  for u in range(len(g)):\n","    for v in g[u]:\n","      indegrees[v]+= 1\n","  print(f'initial indegree : {indegrees}')\n","  V_S = [(indegree, node) for node, indegree in indegrees.items()]\n","  heapq.heapify(V_S)\n","\n","  # Step 2: Kan's algorithm\n","  while len(V_S) > 0:\n","    indegree, first_node = V_S.pop(0)\n","    if indegree != 0: # cycle found, no topological ordering\n","      print(f'Cycle starts at {first_node}')\n","      return None\n","    S.append(first_node)\n","    # Remove edges\n","    for v in g[first_node]:\n","      indegrees[v] -= 1\n","    # update V_S\n","    for idx, (indegree, node) in enumerate(V_S):\n","      if indegree != indegrees[node]:\n","        V_S[idx] = (indegrees[node], node)\n","    heapq.heapify(V_S)\n","  return S"],"execution_count":30,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"sOAJvRU31E3B","executionInfo":{"status":"ok","timestamp":1615934605909,"user_tz":420,"elapsed":1301,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"72ef4c93-01fb-4b15-c4fe-a22a038561a9"},"source":["kahns_topo_sort(dag)"],"execution_count":31,"outputs":[{"output_type":"stream","name":"stdout","text":["initial indegree : defaultdict(<class 'int'>, {0: 0, 1: 1, 2: 2, 3: 0, 4: 1, 5: 1, 6: 1})\n"]},{"output_type":"execute_result","data":{"text/plain":["[0, 1, 3, 2, 4, 5, 6]"]},"metadata":{},"execution_count":31}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"BfQLWZxi0qoC","executionInfo":{"status":"ok","timestamp":1615934605909,"user_tz":420,"elapsed":1293,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"9387a4b9-6be9-4162-e10e-a3ac8fddff4b"},"source":["kahns_topo_sort(dcg)"],"execution_count":32,"outputs":[{"output_type":"stream","name":"stdout","text":["initial indegree : defaultdict(<class 'int'>, {0: 0, 1: 1, 2: 2, 3: 1, 4: 1, 5: 1, 6: 1})\nCycle starts at 2\n"]}]},{"cell_type":"markdown","metadata":{"id":"-L7MyIwoz6T2"},"source":["## DFS"]},{"cell_type":"code","metadata":{"id":"Pf7Jaj8CXWSM","executionInfo":{"status":"ok","timestamp":1615934634337,"user_tz":420,"elapsed":459,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# def dfs(g, s, colors, complete_orders):\n","#   colors[s] = STATE.gray\n","#   no_cycle = True\n","#   for v in g[s]:\n","#     if colors[v] == STATE.white:\n","#       no_cycle = no_cycle and dfs(g, v, colors, complete_orders)\n","#     elif colors[v] == STATE.gray: # a cycle appears\n","#       print(f'Cycle found at node {v}.')\n","#       return False\n","#   colors[s] = STATE.black\n","#   complete_orders.append(s)\n","#   return no_cycle\n","\n","def dfs(g, s, colors, complete_orders):\n","  colors[s] = STATE.gray\n","  for v in g[s]:\n","    if colors[v] == STATE.white:\n","      if dfs(g, v, colors, complete_orders):\n","        return True\n","    elif colors[v] == STATE.gray: # a cycle appears\n","      print(f'Cycle found at node {v}.')\n","      return True\n","  colors[s] = STATE.black\n","  complete_orders.append(s)\n","  return False"],"execution_count":43,"outputs":[]},{"cell_type":"code","metadata":{"id":"hbTw8Pf3YzjJ","executionInfo":{"status":"ok","timestamp":1615934635210,"user_tz":420,"elapsed":328,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def topo_sort(g):\n","  n = len(g)\n","  complete_orders = []\n","  colors = [STATE.white] * n\n","  for i in range(n): # run dfs on all the node\n","    if colors[i] == STATE.white:\n","      if dfs(g, i, colors, complete_orders):\n","        print('Cycle found, no topological ordering')\n","        return None \n","  return complete_orders[::-1]"],"execution_count":44,"outputs":[]},{"cell_type":"code","metadata":{"id":"WeoxmZkcZUKA","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934605911,"user_tz":420,"elapsed":1283,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"df557a8e-8326-4583-a881-4722ce0b3198"},"source":["topo_sort(dag) # [3, 5, 6, 4, 0, 1, 2]\n"],"execution_count":45,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[3, 5, 6, 4, 0, 1, 2]"]},"metadata":{},"execution_count":45}]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"7Ayk_142wAkY","executionInfo":{"status":"ok","timestamp":1615934605911,"user_tz":420,"elapsed":1276,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"5139825a-3352-4221-c1a7-319852b0d848"},"source":["topo_sort(dcg)"],"execution_count":46,"outputs":[{"output_type":"stream","name":"stdout","text":["Cycle found at node 2.\nCycle found, no topological ordering\n"]}]},{"cell_type":"markdown","metadata":{"id":"GTwh1v4l7G2B"},"source":["# Connected Components\n","\n","In the example, we only experiment with BFS. You can use DFS too."]},{"cell_type":"markdown","metadata":{"id":"GCcmT6fusr0E"},"source":["## Undirected Graph"]},{"cell_type":"markdown","metadata":{"id":"okkr1NPJegxk"},"source":["### Graph search approach"]},{"cell_type":"code","metadata":{"id":"HHma4NkEpk_F","executionInfo":{"status":"ok","timestamp":1615934605912,"user_tz":420,"elapsed":1275,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["ug = [[1, 2], [0, 2], [0, 4], [], [2, 3], [6], [5]]"],"execution_count":115,"outputs":[]},{"cell_type":"code","metadata":{"id":"kIPfcNX9ARU7","executionInfo":{"status":"ok","timestamp":1615934605912,"user_tz":420,"elapsed":1273,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def bfs(g, s, state):\n","  state[s] = True\n","  \n","  q, orders = [s], [s]\n","  while q:\n","    u = q.pop(0)\n","    for v in g[u]:\n","      if not state[v]:\n","        state[v] = True\n","        q.append(v)\n","        orders.append(v)\n","  return orders"],"execution_count":116,"outputs":[]},{"cell_type":"code","metadata":{"id":"eH7-zUmhAoDp","executionInfo":{"status":"ok","timestamp":1615934605913,"user_tz":420,"elapsed":1272,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def connectedComponent(g):\n","  n = len(g)\n","  ccs = []\n","  state = [False] * n\n","  for i in range(n):\n","    if not state[i]:\n","      ccs.append(bfs(g, i, state))\n","  return ccs    \n","  "],"execution_count":117,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"5E8IP6vbpYG_","executionInfo":{"status":"ok","timestamp":1615934605913,"user_tz":420,"elapsed":1264,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"fa691fab-185f-4247-a945-6f1089c71dfc"},"source":["connectedComponent(ug)"],"execution_count":118,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[[0, 1, 2, 4, 3], [5, 6]]"]},"metadata":{"tags":[]},"execution_count":118}]},{"cell_type":"markdown","metadata":{"id":"0bf3nLK_ecxS"},"source":["### Union-find approach\n","\n"]},{"cell_type":"markdown","metadata":{"id":"JGAV7iacwLgm"},"source":["Use disjoint set union: https://cp-algorithms.com/data_structures/disjoint_set_union.html\n","\n","http://www.cs.utexas.edu/users/djimenez/utsa/cs3343/lecture18.html"]},{"cell_type":"code","metadata":{"id":"37Ofq3QGesi6","executionInfo":{"status":"ok","timestamp":1615934606066,"user_tz":420,"elapsed":1415,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# implement disjoint set with tree based set representative and path compression\n","class DisjointSet:\n","    def __init__(self, n):\n","        self.n = n\n","        self.p = [i for i in range(n)]\n","\n","    def find(self, x):\n","        if self.p[x] != x:\n","            self.p[x] = self.find(self.p[x])\n","        return self.p[x]\n","\n","    def union(self, x, y):\n","        xr = self.find(x)\n","        yr = self.find(y)\n","        self.p[xr] = yr\n","    \n","    # Add two more functions to visualize the sets\n","    def get_num_sets(self):\n","       return sum(self.find(i) == i for i in range(self.n))\n","\n","    def get_all_sets(self):\n","      sets = defaultdict(set)\n","      for i in range(self.n):\n","        p = self.find(i)\n","        sets[p].add(i)\n","      return sets"],"execution_count":119,"outputs":[]},{"cell_type":"code","metadata":{"id":"6bLTyHvtg_bw","executionInfo":{"status":"ok","timestamp":1615934606067,"user_tz":420,"elapsed":1414,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# implement union-find based connect component detection\n","from collections import defaultdict\n","def connectedComponent(g):\n","  n = len(g)\n","  # initialize disjoint set\n","  ds = DisjointSet(n)\n","\n","  for i in range(n):\n","    for j in g[i]: # for edge i<->j\n","      ds.union(i, j)\n","  return ds.get_num_sets(), ds.get_all_sets() "],"execution_count":120,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"fjGkZI3djyPR","executionInfo":{"status":"ok","timestamp":1615934606067,"user_tz":420,"elapsed":1406,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"5f50ae7b-7784-4bff-f757-bb97fd3cdb08"},"source":["connectedComponent(ug)"],"execution_count":121,"outputs":[{"output_type":"execute_result","data":{"text/plain":["(2, defaultdict(set, {3: {0, 1, 2, 3, 4}, 6: {5, 6}}))"]},"metadata":{"tags":[]},"execution_count":121}]},{"cell_type":"markdown","metadata":{"id":"_3kY3XvFlMG8"},"source":["Dynamic graph"]},{"cell_type":"code","metadata":{"id":"6nVPReRRup2o","executionInfo":{"status":"ok","timestamp":1615934606067,"user_tz":420,"elapsed":1404,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# represent the graph with a list of edges\n","ug_edges = [(0, 1), (0, 2), (1, 2), (2, 4), (4, 3), (4, 3), (5, 6)]"],"execution_count":122,"outputs":[]},{"cell_type":"code","metadata":{"id":"Q2e2Gab8lJ8O","executionInfo":{"status":"ok","timestamp":1615934606068,"user_tz":420,"elapsed":1403,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["class DynamicConnectedComponent():\n","  def __init__(self):\n","    self.ds = DisjointSet(0)\n","    self.node_index= defaultdict(int)\n","    self.index_node = defaultdict(int)\n","    self.index = 0\n","\n","  def add_edge(self, u, v):\n","    if u not in self.node_index:\n","      self.node_index[u], self.index_node[self.index] = self.index, u\n","      self.ds.p.append(self.index)\n","      self.ds.n += 1\n","      self.index += 1\n","      \n","    if v not in self.node_index:\n","      self.node_index[v], self.index_node[self.index] = self.index, v\n","      self.ds.p.append(self.index)\n","      self.ds.n += 1\n","      self.index += 1\n","    u, v = self.node_index[u], self.node_index[v]\n","    self.ds.union(u, v)\n","    return\n","\n","  def get_num_sets(self):\n","    return self.ds.get_num_sets()\n","\n","  def get_all_sets(self):\n","    sets = self.ds.get_all_sets()\n","    return {self.index_node[key] : set([self.index_node[i] for i in list(value)]) for key, value in sets.items()} "],"execution_count":123,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"-Q80jrWeuACg","executionInfo":{"status":"ok","timestamp":1615934606068,"user_tz":420,"elapsed":1395,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"81ebf340-0dcf-43f4-abd1-5e69e201c5bb"},"source":["dcc = DynamicConnectedComponent()\n","for u, v in ug_edges: \n","  dcc.add_edge(u, v)\n","\n","dcc.get_num_sets(), dcc.get_all_sets()"],"execution_count":124,"outputs":[{"output_type":"execute_result","data":{"text/plain":["(2, {3: {0, 1, 2, 3, 4}, 6: {5, 6}})"]},"metadata":{"tags":[]},"execution_count":124}]},{"cell_type":"markdown","metadata":{"id":"G_2ewYbDwVyY"},"source":["## Directed Graph and SCCs\n","https://web.stanford.edu/class/archive/cs/cs161/cs161.1138/lectures/04/Small04.pdf"]},{"cell_type":"code","metadata":{"id":"LpAv9r0OFvLY","executionInfo":{"status":"ok","timestamp":1615934606069,"user_tz":420,"elapsed":1395,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["dg = [[2], [0], [1, 3], [2, 4], [5], [6], []]"],"execution_count":36,"outputs":[]},{"cell_type":"code","metadata":{"id":"u_HBfb1ZGOzG","executionInfo":{"status":"ok","timestamp":1615934606069,"user_tz":420,"elapsed":1393,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# DFS traversal with reversed complete orders\n","def dfs(g, s, colors, complete_orders):\n","  colors[s] = STATE.gray\n","  for v in g[s]:\n","    if colors[v] == STATE.white:\n","      dfs(g, v, colors, complete_orders)\n","  colors[s] = STATE.black\n","  complete_orders.append(s)\n","  return"],"execution_count":37,"outputs":[]},{"cell_type":"code","metadata":{"id":"iFTRlso9GcPp","executionInfo":{"status":"ok","timestamp":1615934606070,"user_tz":420,"elapsed":1392,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# topologically sort in terms of the last node of each scc\n","def topo_sort_scc(g):\n","  v = len(g)\n","  complete_orders = []\n","  colors = [STATE.white] * v\n","  for i in range(v): # run dfs on all the node\n","    if colors[i] == STATE.white:\n","      dfs(g,i, colors, complete_orders)\n","  return complete_orders[::-1]"],"execution_count":38,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"LFeTS3dRG8my","executionInfo":{"status":"ok","timestamp":1615934606070,"user_tz":420,"elapsed":1384,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"9a577218-5e5f-41fa-fd75-c4cf888174a0"},"source":["topo_sort_scc(dg)"],"execution_count":39,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[0, 2, 3, 4, 5, 6, 1]"]},"metadata":{},"execution_count":39}]},{"cell_type":"code","metadata":{"id":"ntT4sgl9lfDf","executionInfo":{"status":"ok","timestamp":1615934606070,"user_tz":420,"elapsed":1382,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# get conversed graph\n","def reverse_graph(g):\n","  rg = [[] for i in range(len(g))]\n","  for u in range(len(g)):\n","    for v in g[u]:\n","      rg[v].append(u)\n","  return rg"],"execution_count":40,"outputs":[]},{"cell_type":"code","metadata":{"id":"iSwBnNlhIgRl","executionInfo":{"status":"ok","timestamp":1615934606071,"user_tz":420,"elapsed":1381,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def scc(g):\n","  rg = reverse_graph(g)\n","  orders = topo_sort_scc(g)\n","\n","  # track states\n","  colors = [STATE.white] * len(g)\n","  sccs = []\n","\n","  # traverse the reversed graph\n","  for u in orders:\n","    if colors[u] != STATE.white:\n","      continue\n","    scc = []\n","    dfs(rg, u, colors, scc)\n","    sccs.append(scc)\n","  return sccs"],"execution_count":41,"outputs":[]},{"cell_type":"code","metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"s9SxP0DvJ0ff","executionInfo":{"status":"ok","timestamp":1615934606071,"user_tz":420,"elapsed":1374,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"977d5e94-aebe-4860-8a36-9272efb34b41"},"source":["scc(dg)"],"execution_count":42,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[[3, 2, 1, 0], [4], [5], [6]]"]},"metadata":{},"execution_count":42}]},{"cell_type":"markdown","metadata":{"id":"YVz-BG3YFJFX"},"source":["# Minimum Spanning Tree\n","\n","https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1138/lectures/24/Slides24.pdf"]},{"cell_type":"markdown","metadata":{"id":"vwa3SlexCQAn"},"source":["## Kruskal's Algorithm"]},{"cell_type":"code","metadata":{"id":"dG6PefDvGh8f","executionInfo":{"status":"ok","timestamp":1615934606201,"user_tz":420,"elapsed":1502,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["from typing import Dict\n","def kruskal(g: Dict):\n","  # g is a dict with node: adjacent nodes\n","  vertices = [i for i in range(1, 1 + len(g))]\n","  vertices = g.keys()\n","  n  = len(vertices)\n","  ver_idx = {v: i for i, v in enumerate(vertices)}\n","\n","  # initialize a disjoint set\n","  ds = DisjointSet(n)\n","\n","  # sort all edges\n","  edges = []\n","  for u in vertices:\n","    for v, w in g[u]:\n","      if (v, u, w) not in edges:\n","        edges.append((u, v, w))\n","  edges.sort(key=lambda x: x[2])\n","  \n","  # main section\n","  A = []\n","  for u, v, w in edges:\n","    if ds.find(ver_idx[u]) != ds.find(ver_idx[v]):\n","      ds.union(ver_idx[u], ver_idx[v])\n","      print(f'{u} -> {v}: {w}')\n","      A.append((u, v, w))\n","  return A"],"execution_count":132,"outputs":[]},{"cell_type":"code","metadata":{"id":"swWe6sHPJ9ed","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606201,"user_tz":420,"elapsed":1494,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"f89684a1-c957-4e24-bf07-0a4cbb3d2cc7"},"source":["a= {1:[(2, 2), (3, 12)], 2:[(1, 2), (3, 4), (5, 5)], 3:[(1, 12), (2, 4), (4, 6), (5, 3)], 4:[(3, 6),  (5, 7)], 5:[(2, 5), (3, 3), (4, 7)]}\n","kruskal(a)"],"execution_count":133,"outputs":[{"output_type":"stream","text":["1 -> 2: 2\n","3 -> 5: 3\n","2 -> 3: 4\n","3 -> 4: 6\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["[(1, 2, 2), (3, 5, 3), (2, 3, 4), (3, 4, 6)]"]},"metadata":{"tags":[]},"execution_count":133}]},{"cell_type":"markdown","metadata":{"id":"tI9aTeoy7Z2p"},"source":["## Prim's Algorithm"]},{"cell_type":"markdown","metadata":{"id":"FurwEn6zCZhP"},"source":["Priority queue by edges"]},{"cell_type":"code","metadata":{"id":"AdLTUkgxAI1I","executionInfo":{"status":"ok","timestamp":1615934606202,"user_tz":420,"elapsed":1493,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["import queue\n","\n","def _get_light_edge(pq, S):\n","  while pq:\n","    # Pick the light edge\n","    w, u, v = pq.get()\n","    # Filter out non-cross edge\n","    if v not in S:\n","      S.add(v)\n","      return (u, v, w)\n","  return None\n","  \n","def prim(g):\n","  cur = 1\n","  n = len(g.items())\n","  S = {cur} #spanning tree set\n","  pq = queue.PriorityQueue()\n","  A = []\n","  \n","  while len(S) < n:\n","    # Expand edges for the exploring vertex\n","    for v, w in g[cur]:\n","      if v not in S:\n","        pq.put((w, cur, v))\n","\n","    le = _get_light_edge(pq, S)\n","    if le:\n","      A.append(le)\n","      cur = le[1] #set the exploring vertex\n","    else:\n","      print(f'Graph {g} is not connected.')\n","      break\n","  return A "],"execution_count":134,"outputs":[]},{"cell_type":"code","metadata":{"id":"40vRdighTR8f","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606202,"user_tz":420,"elapsed":1486,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"2f7b8ffa-3eab-43e3-c82e-562171099767"},"source":["prim(a)"],"execution_count":135,"outputs":[{"output_type":"execute_result","data":{"text/plain":["[(1, 2, 2), (2, 3, 4), (3, 5, 3), (3, 4, 6)]"]},"metadata":{"tags":[]},"execution_count":135}]},{"cell_type":"markdown","metadata":{"id":"hbz06jx0CflB"},"source":["priority queue by vertices"]},{"cell_type":"code","metadata":{"id":"AK0bNYdvkUFG","executionInfo":{"status":"ok","timestamp":1615934606203,"user_tz":420,"elapsed":1485,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["from heapq import heappush, heappop, heapify\n","from typing import List\n","import itertools\n","class PriorityQueue:\n","  def __init__(self, items:List[List]=[]):\n","      self.pq = []                         # list of entries arranged in a heap\n","      self.entry_finder = {}               # mapping of tasks to entries\n","      self.REMOVED = '<removed-task>'      # placeholder for a removed task\n","      self._counter = itertools.count()     # unique sequence count, this is hidden from user\n","      # add count to items\n","      for p, t, info in items:\n","        item = [p, next(self._counter), t, info]\n","        self.entry_finder[t] = item\n","        self.pq.append(item)\n","      heapify(self.pq)\n","        \n","  def add_task(self, task, priority=0, info=None): # O(logE)\n","      'Add a new task or update the priority of an existing task'\n","      'the old task is removed from entry_finder but still remained in the heapq'\n","      if task in self.entry_finder:\n","          self._remove_task(task)\n","      count = next(self._counter)\n","      entry = [priority, count, task, info]\n","      self.entry_finder[task] = entry\n","      heappush(self.pq, entry)\n","      \n","  def _remove_task(self, task, info=None):# O(1)\n","      'Mark an existing task as REMOVED.  Raise KeyError if not found.'\n","      entry = self.entry_finder.pop(task)\n","      entry[-2] = self.REMOVED\n","\n","  def pop_task(self): #O(logE)\n","      'Remove and return the lowest priority task. Raise KeyError if empty.'\n","      while self.pq:\n","          priority, count, task, info = heappop(self.pq)\n","          if task is not self.REMOVED:\n","              del self.entry_finder[task]\n","              return task, info, priority\n","      raise KeyError('pop from an empty priority queue')\n","      \n","  def get_task(self, taskid):\n","    '''return task information given task id'''\n","    if taskid in self.entry_finder:\n","      p, _, t, info = self.entry_finder[taskid]\n","      return p, info\n","    else:\n","      return None, None\n","  \n","  def empty(self):\n","    return not self.entry_finder"],"execution_count":136,"outputs":[]},{"cell_type":"code","metadata":{"id":"kjms2ztVkVYE","executionInfo":{"status":"ok","timestamp":1615934606358,"user_tz":420,"elapsed":1637,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def prim2(g):  \n","  n = len(g.items())\n","  pq = PriorityQueue()\n","  S = {}\n","  A = []\n","  # Initialization\n","  for i in range(n):\n","    pq.add_task(task=i+1, priority=float('inf'), info=None) # task: vertex, priority: edge cost, info: predecessor vertex\n","  \n","  S = {1}\n","  pq.add_task(1, 0, info=1)\n","\n","  while len(S) < n:\n","    u, p, w = pq.pop_task()\n","    if w == float('inf'):\n","      print(f'Graph {g} is not connected.')\n","      break\n","    A.append((p, u, w))\n","    S.add(u)\n","    for v, w in g[u]:\n","      if v not in S and  w < pq.entry_finder[v][0]:\n","        pq.add_task(v, w, u)\n","  \n","  return A\n"],"execution_count":137,"outputs":[]},{"cell_type":"code","metadata":{"id":"0C0dHcnDmD8_","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606361,"user_tz":420,"elapsed":1633,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"70876a2f-cac6-424e-9392-280c95f79e58"},"source":["print(prim2(a))"],"execution_count":138,"outputs":[{"output_type":"stream","text":["[(1, 1, 0), (1, 2, 2), (2, 3, 4), (3, 5, 3), (3, 4, 6)]\n"],"name":"stdout"}]},{"cell_type":"markdown","metadata":{"id":"y7Qv3DhRCBnw"},"source":["# Shortest Path\n","\n","\n","1.   brute force solution\n","2.   illustrating the overleapping subproblem\n","3.   illustrating the optimal subproblems\n","4.   Introduce bellman-ford algorithm\n","5.   introduce dijkstra algorithm\n","\n","Questions:\n","1. detect the negative weight cycle\n","\n","\n"]},{"cell_type":"markdown","metadata":{"id":"CadIdLB8CepE"},"source":["#### Single Source Shortest Path"]},{"cell_type":"code","metadata":{"id":"pQJt2NkhD2re","executionInfo":{"status":"ok","timestamp":1615934606361,"user_tz":420,"elapsed":1631,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["import sys\n","from collections import defaultdict\n","g = {\n","    's':[('t', 6), ('y', 7)],\n","    't':[('x', 5), ('y', 8), ('z', -4)],\n","    'x':[('t',-2)],\n","    'y':[('x',-3), ('z',9)],\n","    'z':[('x',7)]    \n","}\n","\n","g1 = {\n","    's':[('t', 6), ('y', 7)],\n","    't':[('x', -5), ('y', 8), ('z', -4)],\n","    'x':[('t',2)],\n","    'y':[('x',-3), ('z',9)],\n","    'z':[('x',7)]    \n","}"],"execution_count":139,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"cHGikfV_qfRZ"},"source":["Backtracking to enumerate all paths from start vertex and its cost. The following code works for both undirected and directed graph.\n","\n"]},{"cell_type":"code","metadata":{"id":"S4qg5yO5qGue","executionInfo":{"status":"ok","timestamp":1615934606362,"user_tz":420,"elapsed":1630,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def all_paths(g, s, path, cost, ans):\n","  ans.append({'path': path[::], 'cost': cost})\n","  for v, w in g[s]:\n","    if v in path:\n","      continue\n","    path.append(v)\n","    cost += w\n","    all_paths(g, v, path, cost, ans)\n","    cost -= w\n","    path.pop()"],"execution_count":140,"outputs":[]},{"cell_type":"code","metadata":{"id":"Hd1BvnAMuVtA","executionInfo":{"status":"ok","timestamp":1615934606362,"user_tz":420,"elapsed":1628,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def get_shortest_path(ans, g):\n","  delta = {v: float('inf') for v in g.keys()} # shortest path value from s to all vertices\n","  delta_path = {v: [] for v in g.keys()}\n","  for item in ans:\n","    path = item['path']\n","    cost = item['cost']\n","    target = path[-1]\n","    if cost < delta[target]:\n","      delta[target] = cost\n","      delta_path[target] = path\n","  return delta, delta_path"],"execution_count":141,"outputs":[]},{"cell_type":"code","metadata":{"id":"kluInb73SATW","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606363,"user_tz":420,"elapsed":1622,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"d9dbbbef-c55f-47c3-906b-b11d8eef35c7"},"source":["ans, path, cost = [], ['s'], 0\n","all_paths(g, 's', path, cost, ans  )\n","get_shortest_path(ans, g)"],"execution_count":142,"outputs":[{"output_type":"execute_result","data":{"text/plain":["({'s': 0, 't': 2, 'x': 4, 'y': 7, 'z': -2},\n"," {'s': ['s'],\n","  't': ['s', 'y', 'x', 't'],\n","  'x': ['s', 'y', 'x'],\n","  'y': ['s', 'y'],\n","  'z': ['s', 'y', 'x', 't', 'z']})"]},"metadata":{"tags":[]},"execution_count":142}]},{"cell_type":"code","metadata":{"id":"4bJG_oCYbbCW","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606363,"user_tz":420,"elapsed":1613,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"107d3daa-c486-4818-a58e-61b9ad9aa29b"},"source":["# on graph 2\n","ans1, path, cost = [], ['s'], 0\n","all_paths(g1, 's', path, cost, ans1  )\n","get_shortest_path(ans1, g1)"],"execution_count":143,"outputs":[{"output_type":"execute_result","data":{"text/plain":["({'s': 0, 't': 6, 'x': 1, 'y': 7, 'z': 2},\n"," {'s': ['s'],\n","  't': ['s', 't'],\n","  'x': ['s', 't', 'x'],\n","  'y': ['s', 'y'],\n","  'z': ['s', 't', 'z']})"]},"metadata":{"tags":[]},"execution_count":143}]},{"cell_type":"markdown","metadata":{"id":"mnmQXroqDybK"},"source":["## The Bellman-Ford Algorithm\n","Use the dp vector and W"]},{"cell_type":"code","metadata":{"id":"VSNGROmJjX4m","executionInfo":{"status":"ok","timestamp":1615934606364,"user_tz":420,"elapsed":1612,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["g = {\n","    's':[('t', 6), ('y', 7)],  \n","    't':[('x', 5), ('y', 8), ('z', -4)],\n","    'x':[('t',-2)],\n","    'y':[('x',-3), ('z',9)],\n","    'z':[('x',7)],\n","}"],"execution_count":144,"outputs":[]},{"cell_type":"code","metadata":{"id":"VTeWqtP1kXvJ","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606364,"user_tz":420,"elapsed":1605,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"c5439c08-1935-4431-8c17-699ec3010e2b"},"source":["# convert g to W\n","n = len(g)\n","W = [[float('inf') for _ in range(n)] for _ in range(n)]\n","# Assign an enumerial index for each key\n","V = g.keys()\n","# Key : index\n","ver2idx = dict(zip(V, [i for i in range(n)]))\n","# Index : key\n","idx2ver = dict(zip([i for i in range(n)], V))\n","print(f'ver2idx : {ver2idx}')\n","print(f'idx2ver :{idx2ver}')\n","for u in V:\n","  ui = ver2idx[u]\n","  W[ui][ui] = 0\n","  for v, w in g[u]:\n","    vi = ver2idx[v]\n","    W[ui][vi] = w\n","W"],"execution_count":145,"outputs":[{"output_type":"stream","text":["ver2idx : {'s': 0, 't': 1, 'x': 2, 'y': 3, 'z': 4}\n","idx2ver :{0: 's', 1: 't', 2: 'x', 3: 'y', 4: 'z'}\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["[[0, 6, inf, 7, inf],\n"," [inf, 0, 5, 8, -4],\n"," [inf, -2, 0, inf, inf],\n"," [inf, inf, -3, 0, 9],\n"," [inf, inf, 7, inf, 0]]"]},"metadata":{"tags":[]},"execution_count":145}]},{"cell_type":"code","metadata":{"id":"Cd01eGEMmYT6","executionInfo":{"status":"ok","timestamp":1615934606523,"user_tz":420,"elapsed":1762,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["## using W\n","def bellman_ford_dp(s, W):\n","  n = len(W)\n","  # D, pi\n","  D = [float('inf') if i!=s else 0 for i in range(n)] # * n\n","  P = [None] * n\n","  for m in range(n-1): \n","    newD = D[:]\n","    for i in range(n): # endpoint\n","      for k in range(n): # intermediate node\n","        if D[k] + W[k][i] < newD[i]:\n","          P[i] = k\n","          newD[i] = D[k] + W[k][i]\n","\n","    D = newD\n","    print(f'D{m+1}: {D}')\n","  return D, P"],"execution_count":146,"outputs":[]},{"cell_type":"code","metadata":{"id":"aDhmuNoaozPZ","executionInfo":{"status":"ok","timestamp":1615934606524,"user_tz":420,"elapsed":1761,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# print the path from s-> u through backtracking starting from u\n","def get_path(P, s, u, path):\n","  path.append(u)\n","  if u == s:\n","    print('Reached to the source vertex, stop!')\n","    return path[::-1]\n","  elif u is None:\n","    print(f\"No path found between {s} and {u}.\")\n","    return [] \n","  else:  \n","    return get_path(P, s, P[u], path)"],"execution_count":147,"outputs":[]},{"cell_type":"code","metadata":{"id":"ySPWM5kkm2D6","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606524,"user_tz":420,"elapsed":1753,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"cffa0a59-0c7f-414f-c2f0-1aae2aa241c4"},"source":["D, P = bellman_ford_dp(0, W)\n","D, P"],"execution_count":148,"outputs":[{"output_type":"stream","text":["D1: [0, 6, inf, 7, inf]\n","D2: [0, 6, 4, 7, 2]\n","D3: [0, 2, 4, 7, 2]\n","D4: [0, 2, 4, 7, -2]\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["([0, 2, 4, 7, -2], [None, 2, 3, 0, 1])"]},"metadata":{"tags":[]},"execution_count":148}]},{"cell_type":"code","metadata":{"id":"MoOy9-_Ho1Gg","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606525,"user_tz":420,"elapsed":1746,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"ce4ae8c1-f61b-40d7-e5d0-43264fbd3b9f"},"source":["get_path(P, 0, 4, [])"],"execution_count":149,"outputs":[{"output_type":"stream","text":["Reached to the source vertex, stop!\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["[0, 3, 2, 1, 4]"]},"metadata":{"tags":[]},"execution_count":149}]},{"cell_type":"markdown","metadata":{"id":"0XuSoy4Ln7gf"},"source":["Formal bellman-ford algorithm"]},{"cell_type":"code","metadata":{"id":"d0riQJZqIdKU","executionInfo":{"status":"ok","timestamp":1615934606525,"user_tz":420,"elapsed":1744,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["g = {\n","    's':[('t', 6), ('y', 7)],  \n","    't':[('x', 5), ('y', 8), ('z', -4)],\n","    'x':[('t',-2)],\n","    'y':[('x',-3), ('z',9)],\n","    'z':[('x',7)],\n","}"],"execution_count":150,"outputs":[]},{"cell_type":"code","metadata":{"id":"ZwEC3YcXFdQc","executionInfo":{"status":"ok","timestamp":1615934606526,"user_tz":420,"elapsed":1744,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def bellman_ford(g: dict, s: str):\n","  n = len(g)\n","  # Assign an enumerial index for each key\n","  V = g.keys()\n","  # Key to index\n","  ver2idx = dict(zip(V, [i for i in range(n)]))\n","  # Index to key\n","  idx2ver = dict(zip([i for i in range(n)], V))\n","  # Initialization the dp matrix with d estimate and predecessor\n","  si = ver2idx[s]\n","  D = [float('inf') if i!=si else 0 for i in range(n)] # * n\n","  P = [None] * n\n","  \n","  # n-1 passes\n","  for i in range(n-1): \n","    # relax all edges\n","    for u in V:\n","      ui = ver2idx[u]\n","      for v, w in g[u]:\n","        vi = ver2idx[v]\n","        # Update dp's minimum path value and predecessor\n","        if D[vi] > D[ui] + w:\n","          D[vi] = D[ui] + w\n","          P[vi] = ui\n","    print(f'D{i+1}: {D}')  \n","  return D, P, ver2idx, idx2ver"],"execution_count":151,"outputs":[]},{"cell_type":"code","metadata":{"id":"IpwrrrIDQMk2","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934606526,"user_tz":420,"elapsed":1736,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"6c0f9f78-9a4e-4187-b540-b54901efb60d"},"source":["bellman_ford(g, 's')"],"execution_count":152,"outputs":[{"output_type":"stream","text":["D1: [0, 6, 4, 7, 2]\n","D2: [0, 2, 4, 7, 2]\n","D3: [0, 2, 4, 7, -2]\n","D4: [0, 2, 4, 7, -2]\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["([0, 2, 4, 7, -2],\n"," [None, 2, 3, 0, 1],\n"," {'s': 0, 't': 1, 'x': 2, 'y': 3, 'z': 4},\n"," {0: 's', 1: 't', 2: 'x', 3: 'y', 4: 'z'})"]},"metadata":{"tags":[]},"execution_count":152}]},{"cell_type":"markdown","metadata":{"id":"rIsYCsv7hGMs"},"source":["Implement a version that plots the process, and use HTML-like to draw the graph with math symbols: https://stackoverflow.com/questions/9684807/how-to-insert-mathematical-symbols-like-greek-characters-in-a-graphviz-dot-file/41346289#41346289"]},{"cell_type":"markdown","metadata":{"id":"s_RLJ0PTxEFT"},"source":["Optimization with topologial sort"]},{"cell_type":"code","metadata":{"id":"fzuM1j5zxMCc","executionInfo":{"status":"ok","timestamp":1615934651235,"user_tz":420,"elapsed":202,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# dag and the ordering is topological sorted order already\n","dag = {\n","    's':[('t', 6), ('y', 7)], \n","    't':[('x', 5), ('y', 8), ('z', -4)],\n","    'y':[('x',-3), ('z',9)],\n","    'z':[('x',7)],\n","    'x':[],  \n","}"],"execution_count":48,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"WP9baC0K4p2m"},"source":["Linear Bellman-ford algorithm for DAG."]},{"cell_type":"code","metadata":{"id":"hwqQth1H4tpy","executionInfo":{"status":"ok","timestamp":1615934606664,"user_tz":420,"elapsed":1866,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def bellman_ford_dag(g, s):\n","  s = s\n","  n = len(g)\n","  # Key to index\n","  ver2idx = dict(zip(g.keys(), [i for i in range(n)]))\n","  # Index to key\n","  idx2ver = dict(zip([i for i in range(n)], g.keys()))\n","  print(ver2idx)\n","  # Convert g to index\n","  ng = [[] for _ in range(n)]\n","  for u in g.keys():\n","    for v, _ in g[u]:\n","      ui = ver2idx[u]\n","      vi = ver2idx[v]\n","      ng[ui].append(vi)\n","  print(ng)\n","  V = topo_sort(ng)\n","  print(V)\n","  # Initialization the dp matrix with d estimate and predecessor\n","  si = ver2idx[s]\n","  dp = [(float('inf'), None) for i in range(n)]\n","  dp[si] = (0, None)\n","\n","  # relax all edges\n","  for ui in V:\n","    u = idx2ver[ui]\n","    for v, w in g[u]:\n","      vi = ver2idx[v]\n","      # Update dp's minimum path value and predecessor\n","      if dp[vi][0] > dp[ui][0] + w:\n","        dp[vi] = (dp[ui][0] + w, ui)\n","  return dp"],"execution_count":47,"outputs":[]},{"cell_type":"code","metadata":{"id":"bI74keuR6KKo","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934655544,"user_tz":420,"elapsed":294,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"b2956f78-e27a-4b6d-98b1-5ce0409bdb76"},"source":["bellman_ford_dag(dag, 's')"],"execution_count":50,"outputs":[{"output_type":"stream","name":"stdout","text":["{'s': 0, 't': 1, 'y': 2, 'z': 3, 'x': 4}\n[[1, 2], [4, 2, 3], [4, 3], [4], []]\n[0, 1, 2, 3, 4]\n"]},{"output_type":"execute_result","data":{"text/plain":["[(0, None), (6, 0), (7, 0), (2, 1), (4, 2)]"]},"metadata":{},"execution_count":50}]},{"cell_type":"markdown","metadata":{"id":"MRUhFcSQ0wHS"},"source":["## Dijkstra"]},{"cell_type":"code","metadata":{"id":"Sy6OITLr1swv","executionInfo":{"status":"ok","timestamp":1615934663408,"user_tz":420,"elapsed":291,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["g = {\n","    's':[('t', 6), ('y', 7)], \n","    't':[('x', 5), ('y', 8), ('z', 4)],\n","    'y':[('x', 3), ('z', 9)],\n","    'z':[('x', 7)],\n","    'x':[('t', 2)],  \n","}\n","\n","g = {\n","    '0':[('1', 50), ('2', 30), ('3', 100), ('4', 10)], \n","    '1':[('0', 50), ('2', 5), ('3', 20)],\n","    '2':[('1', 5), ('3', 6), ('0', 30)],\n","    '3':[('0', 100), ('1', 20), ('2', 6), ('4', 20)],\n","    '4':[('0', 10),('3', 20)],  \n","}\n","\n"],"execution_count":164,"outputs":[]},{"cell_type":"code","metadata":{"id":"vxCW0Bg0XfaZ","executionInfo":{"status":"aborted","timestamp":1615934606819,"user_tz":420,"elapsed":2010,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["g"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"ADsUVzERjePf","executionInfo":{"status":"aborted","timestamp":1615934606820,"user_tz":420,"elapsed":2009,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["plot_graph(g, name=\"directed_nonnegative_graph\")"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"dH-Jq9Hs006V","executionInfo":{"status":"aborted","timestamp":1615934606820,"user_tz":420,"elapsed":2007,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["\n","from typing import List, Tuple\n","import sys\n","\n","def initialize(Q, g, s):\n","  # put all edges into q\n","  for k in g.keys():\n","    Q.add_task(task=k, priority=sys.maxsize, info=None ) #task id is the id, info is the predecessor\n","  # set weight for vertices one edge away from source\n","  Q.add_task(task=s, priority=0, info=None)\n","  for id, w in g[s]:\n","    Q.add_task(task=id, priority=w, info=s) # weight, id, predecessor\n","\n","      \n","def extract_min(Q:List[Tuple]):\n","  '''extra minimum vertex with the weight using priority queue'''\n","  task, info, pri = Q.pop_task()\n","  return task, pri, info\n","\n","def update(Q, g, cid, cw):\n","  '''current id, w, p'''\n","  for id, w in g[cid]: #target\n","    pw, pp = Q.get_task(id)\n","    if not pw and not pp: # already found the shortest path for this id\n","      continue\n","    new_w, new_p = w, pp\n","    #print(cw, w, pw)\n","    if cw + w < pw:\n","      new_w = cw + w\n","      new_p = cid\n","      Q.add_task(task=id, priority=new_w, info=new_p)\n","  \n","def dijkstra(g, s):\n","  ''' '''\n","  Q = PriorityQueue() # the set of all edges, \n","  S = []\n","  # initialize\n","  initialize(Q, g, s)\n","  while not Q.empty():\n","    min_id, min_w, p = extract_min(Q)\n","    print(min_id, min_w, p)\n","    S.append((min_id, min_w, p))\n","    # need to update weight in the queue \n","    update(Q, g, min_id, min_w)\n","  return S"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"2Bg32B4B7tGb","executionInfo":{"status":"aborted","timestamp":1615934606821,"user_tz":420,"elapsed":2006,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["S=dijkstra(g, '0')\n","print(S)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"rKc5rfmc32fd","executionInfo":{"status":"aborted","timestamp":1615934606822,"user_tz":420,"elapsed":2005,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def dijkstra(g, s):\n","  Q = PriorityQueue()\n","  S = []\n","  # task: vertex id, priority: shortest-path estimate, info: predecessor\n","  Q.add_task(task=s, priority=0, info=None)\n","  visited = set()\n","  while not Q.empty():\n","    # Use the light vertex\n","    u, up, ud = Q.pop_task()\n","    visited.add(u)\n","    S.append((u, ud, up))\n","\n","    # Relax adjacent vertice\n","    for v, w in g[u]: \n","      # Already found the shortest path for this id\n","      if v in visited: \n","        continue\n","      \n","      vd, vp = Q.get_task(v)\n","      # First time to add the task or already in the queue, but need update \n","      if not vd  or ud + w < vd:\n","        Q.add_task(task=v, priority=ud + w, info=u)\n","  return S"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"zWY2bDRw-ovd","executionInfo":{"status":"aborted","timestamp":1615934606822,"user_tz":420,"elapsed":2003,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["dijkstra(g, 's')"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"Czgsme2nrqu0"},"source":["Get visualization"]},{"cell_type":"code","metadata":{"id":"ntV9ILEFrpvx","executionInfo":{"status":"aborted","timestamp":1615934606823,"user_tz":420,"elapsed":2002,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def plot_subgraph(dot, v_pos, g, Q, index):\n","  #dot = Digraph(comment='directed_graph', engine=\"neato\", format='png', strict=True, )\n","  dot.attr(_attributes={'fontsize': '15'})\n","  name = ''\n","  if index == 0:\n","    for u, p in v_pos.items(): #label shows in the node, it is also what represents each node\n","      x, y = p.split(',')\n","      #p = str(int(x)+5*(index+1)) + ',' + y\n","      xlabel = '<&infin;>'\n","      # label is the one showing within the node, and name act as the name used in the edge, and xlabel is the tag above each node\n","      dot.node(name=u+name, label=xlabel, xlabel = u, _attributes={'pos': str(p), 'penwidth': \"1.5\"})\n","      for v, w in g[u]:\n","        dot.edge(tail_name=u+name, head_name=v+name, _attributes={'xlabel': str(w), 'penwidth': \"1.5\"})\n","\n","  for vd, _, v, u in Q.pq:\n","    if v == Q.REMOVED:\n","      continue\n","    dot.node(name=v+name, label=str(vd), xlabel=v, _attributes={'color': 'red', 'penwidth': \"1.5\"})\n","    if u is not None:\n","      dot.edge(u+name, v+name, _attributes={'color': 'red', 'penwidth': \"1.5\" })\n","    #init.view()\n","  dot.render(f'test-output/dijkstra_{index}', view=True, format='png') \n","\n","def dijkstra_fig(g, s):\n","  Q = PriorityQueue()\n","  S = []\n","  # task: vertex id, priority: shortest-path estimate, info: predecessor\n","  Q.add_task(task=s, priority=0, info=None)\n","  visited = set()\n","  v_pos = {'s': '0,0!', 't': '1,1!', 'x': '3, 1!', 'y': '1,-1!', 'z': '3,-1!'}\n","  idx = 0\n","  dot = Digraph(comment='directed_graph', engine=\"neato\", format='png', strict=True, )\n","  plot_subgraph(dot, v_pos, g, Q, idx)\n","  while not Q.empty():\n","    # get all edges\n","    idx += 1\n","    # Use the light vertex\n","    # Update set S\n","    u, up, ud = Q.pop_task()\n","    dot.node(name=u, label=str(ud), xlabel = u, _attributes={'pos': v_pos[u], 'penwidth': \"1.5\", 'color': 'blue'})\n","     \n","    if up is not None:\n","      dot.edge(up, u, _attributes={'color': 'blue', 'penwidth': \"1.5\" })\n","    dot.render(f'test-output/dijkstra_{idx-1+0.5}', view=True, format='png') \n","\n","    visited.add(u)\n","    S.append((u, ud, up))\n","\n","    # Relax adjacent vertice\n","    for v, w in g[u]: \n","      # Already found the shortest path for this id\n","      if v in visited: \n","        continue\n","      \n","      vd, vp = Q.get_task(v)\n","      # First time to add the task or already in the queue, but need update \n","      if not vd  or ud + w < vd:\n","        Q.add_task(task=v, priority=ud + w, info=u)\n","\n","        # return the old edge to normal\n","        if vd is not None and ud + w < vd:\n","          dot.edge(vp, v, _attributes={'color': 'black', 'penwidth': \"1.5\" })\n","        # Expand edges and return the old edges to normal\n","    plot_subgraph(dot, v_pos, g, Q, idx)        \n","  return S, dot"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"qYgb1KFbvKtP","executionInfo":{"status":"aborted","timestamp":1615934606823,"user_tz":420,"elapsed":2000,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["dijkstra_fig(g, 's')"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"6WHcUsLy2FH4"},"source":["##All-pairs shortest paths\n","* Extension on Bellman-Ford algorithm\n","* Extension on Dijkstra's algorithm"]},{"cell_type":"markdown","metadata":{"id":"VOn2dU_WB1uC"},"source":["##### Extended Bellman-ford algorithm"]},{"cell_type":"code","metadata":{"id":"i_MZSUd5gef-","executionInfo":{"status":"aborted","timestamp":1615934606823,"user_tz":420,"elapsed":1998,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# rewrite the non negative weight graph g as\n","g = {\n","    's':[('t', 6), ('y', 7)],\n","    't':[('x', 5), ('y', 8), ('z', -4)],\n","    'x':[('t',-2)],\n","    'y':[('x',-3), ('z',9)],\n","    'z':[('x',7)]    \n","}\n","n = len(g)\n","W = [[float('inf') for _ in range(n)] for _ in range(n)]\n","key2idx = {k : i for k, i in zip(g.keys(), range(n))}\n","idx2key = {i : k for k, i in zip(g.keys(), range(n))}\n","for u in g.keys():\n","  ui = key2idx[u]\n","  W[ui][ui] = 0\n","  for v, w in g[u]:\n","    vi = key2idx[v]\n","    W[ui][vi] =  w\n","W, key2idx, idx2key"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"I36J1RUw3Br0","executionInfo":{"status":"aborted","timestamp":1615934606824,"user_tz":420,"elapsed":1997,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["import copy\n","def bellman_ford(W, L):\n","  n = len(W)\n","  for i in range(n): # source\n","    for j in range(n): # endpoint\n","      for k in range(n): # extend one edge\n","        L[i][j] = min(L[i][j], L[i][k]+W[k][j])\n","  \n","def extended_bellman_ford(W):\n","  n = len(W)\n","  # initialize L, first pass\n","  L = copy.deepcopy(W)\n","  print(f'L1 : {L} \\n')\n","  # n-2 passes\n","  for i in range(n-2):\n","    bellman_ford(W, L)\n","    print(f'L{i+2}: {L} \\n')\n","  return L"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"0NqRr1nelDoh","executionInfo":{"status":"aborted","timestamp":1615934606824,"user_tz":420,"elapsed":1995,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["L = extended_bellman_ford(W)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"NkkqO3kyrau4"},"source":["Implement a version that tracks the predecessor\n"]},{"cell_type":"code","metadata":{"id":"9Y3wf294rZ3W","executionInfo":{"status":"aborted","timestamp":1615934606825,"user_tz":420,"elapsed":1994,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["import copy\n","def bellman_ford_with_predecessor(W, L, P):\n","  n = len(W)\n","  for i in range(n): # source\n","    for j in range(n): # endpoint\n","      for k in range(n): # extend one edge\n","        if L[i][k] + W[k][j] < L[i][j]:\n","          L[i][j] = L[i][k] + W[k][j] # set d\n","          P[i][j] = k # set predecessor\n","  \n","def extended_bellman_ford_with_predecessor(W):\n","  n = len(W)\n","  # initialize L, first pass\n","  L = copy.deepcopy(W)\n","  print(f'L1 : {L} \\n')\n","  P = [[None for _ in range(n)] for _ in range(n)]\n","  for i in range(n):\n","    for j in range(n):\n","      if L[i][j] != 0 and L[i][j] != float('inf'):\n","        P[i][j] = i\n","  # n-2 passes\n","  for i in range(n-2):\n","    bellman_ford_with_predecessor(W, L, P)\n","    print(f'L{i+2}: {L} \\n')\n","  return L, P"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"Xll1FnsYqlNZ","executionInfo":{"status":"aborted","timestamp":1615934606825,"user_tz":420,"elapsed":1993,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# print the path from s-> u through backtracking starting from u\n","def print_path(P, s, u, path):\n","  path.append(u)\n","  if u == s:\n","    print('Reached to the source vertex, stop!')\n","    return path[::-1]\n","  elif u is None:\n","    print(f\"No path found between {s} and {u}.\")\n","    return []\n","  else:  \n","    return print_path(P, s, P[s][u], path)"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"3TUUdrwltp8J","executionInfo":{"status":"aborted","timestamp":1615934606826,"user_tz":420,"elapsed":1992,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["L, P = extended_bellman_ford_with_predecessor(W)\n","L, P"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"56UUV3ljq6SD","executionInfo":{"status":"aborted","timestamp":1615934606826,"user_tz":420,"elapsed":1991,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["# get path from s to t\n","path = print_path(P, key2idx['t'], key2idx['z'], [])\n","path = [idx2key[i] for i in path]\n","path"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"Q5FL1hXGyNll","executionInfo":{"status":"aborted","timestamp":1615934606829,"user_tz":420,"elapsed":1992,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["#Find edges for each shortest_path tree\n","shortest_path_trees = [[] for _ in range(n)]\n","for i in range(n):\n","  for j in range(n):\n","    path = print_path(P, i, j, [])\n","    for u, v in zip(path[:-1], path[1:]):\n","      if (u, v) not in shortest_path_trees[i]:\n","        shortest_path_trees[i].append((u, v))\n","# now replace it all to keys\n","shortest_path_tree_dic = {}\n","for i in range(len(shortest_path_trees)):\n","  s = idx2key[i]\n","  if s not in shortest_path_tree_dic:\n","    shortest_path_tree_dic[s] = []\n","  for u, v in shortest_path_trees[i]:\n","    shortest_path_tree_dic[s].append((idx2key[u], idx2key[v]))\n","shortest_path_tree_dic"],"execution_count":null,"outputs":[]},{"cell_type":"code","metadata":{"id":"j6s6Uauc3AVz","executionInfo":{"status":"aborted","timestamp":1615934606829,"user_tz":420,"elapsed":1990,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["from google.colab.patches import cv2_imshow\n","import cv2\n","\n","for idx, s in enumerate(list(shortest_path_tree_dic.keys())):\n","  # stric so that one edge wont be repeat but keep the last time's edit\n","  dot = Digraph(comment='directed_graph', engine=\"neato\", format='png', strict=True)\n","  # Generate grapg\n","  v_pos = {'s': '0,0!', 't': '1,1!', 'x': '3, 1!', 'y': '1,-1!', 'z': '3,-1!'}\n","  for u, p in v_pos.items():\n","    dot.node(u, _attributes={'pos': str(p), 'fillcolor': \"#d62728\"})\n","    for v, w in g[u]:\n","      dot.edge(u, v, _attributes={'xlabel': str(w)})\n","  \n","  # Color one tree\n","  colors = ['red', 'green', 'yellow', 'blue', 'purple']\n","  dot.node(s, _attributes={'pos': str(v_pos[s]), 'color': colors[idx]})\n","  for x, y in shortest_path_tree_dic[s]:\n","    dot.edge(x, y, _attributes={'color': colors[idx]}  )\n","\n","  dot.render(f'test-output/shortest_path_trees_{idx}', view=True) \n","  img = cv2.imread(f'test-output/shortest_path_trees_{idx}.png')\n","  cv2_imshow(img)"],"execution_count":null,"outputs":[]},{"cell_type":"markdown","metadata":{"id":"o3BQwl5klO5t"},"source":["##### Repeated Square \n","\n"]},{"cell_type":"code","metadata":{"id":"UuT9mjAdluQ7","executionInfo":{"status":"ok","timestamp":1615934692405,"user_tz":420,"elapsed":323,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["import copy\n","import math\n","def bellman_ford_repeated_square(L):\n","  n = len(W)\n","  for i in range(n): # source\n","    for j in range(n): # endpoint\n","      for k in range(n): # double the extending length\n","        L[i][j] = min(L[i][j], L[i][k]+L[k][j])\n","  \n","def extended_bellman_ford_repeated_square(W):\n","  n = len(W)\n","  # initialize L, first pass\n","  L = copy.deepcopy(W)\n","  print(f'L1 : {L} \\n')\n","  # log n passes\n","  for i in range(math.ceil(math.log(n))):\n","    bellman_ford_repeated_square(L)\n","    print(f'L{2^(i+1)}: {L} \\n')\n","  return L"],"execution_count":165,"outputs":[]},{"cell_type":"code","metadata":{"id":"LVYfDIC3mfsf","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934693859,"user_tz":420,"elapsed":314,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"43e1804b-0f21-4243-af36-2bdc16080775"},"source":["L = extended_bellman_ford_repeated_square(W)"],"execution_count":166,"outputs":[{"output_type":"stream","text":["L1 : [[0, 6, inf, 7, inf], [inf, 0, 5, 8, -4], [inf, -2, 0, inf, inf], [inf, inf, -3, 0, 9], [inf, inf, 7, inf, 0]] \n","\n","L3: [[0, 6, 4, 7, 2], [inf, 0, 3, 8, -4], [inf, -2, 0, 6, -6], [inf, -5, -3, 0, -9], [inf, 5, 7, 13, 0]] \n","\n","L0: [[0, 2, 4, 7, -2], [inf, 0, 3, 8, -4], [inf, -2, 0, 6, -6], [inf, -5, -3, 0, -9], [inf, 5, 7, 13, 0]] \n","\n"],"name":"stdout"}]},{"cell_type":"code","metadata":{"id":"7TVAk4QRm8LW","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934696007,"user_tz":420,"elapsed":280,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"4bdb9f8d-c31b-48a2-9f0e-8a3511c1f8ba"},"source":["math.ceil(math.log(5))"],"execution_count":167,"outputs":[{"output_type":"execute_result","data":{"text/plain":["2"]},"metadata":{"tags":[]},"execution_count":167}]},{"cell_type":"markdown","metadata":{"id":"4om6uVmvB8Zd"},"source":["#####The Floyd-Warshall Algorithm"]},{"cell_type":"code","metadata":{"id":"XpXn11SKCJoL","executionInfo":{"status":"ok","timestamp":1615934754533,"user_tz":420,"elapsed":307,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}}},"source":["def floyd_warshall(W):\n","  L = copy.deepcopy(W) #L0\n","  n = len(W)\n","  for k in range(n): # intermediate node\n","    for i in range(n): # start node\n","      for j in range(n): # end node\n","        L[i][j] = min(L[i][j], L[i][k] + L[k][j])\n","  print(L)\n","  return L"],"execution_count":172,"outputs":[]},{"cell_type":"code","metadata":{"id":"ZQTdHMQyobD0","colab":{"base_uri":"https://localhost:8080/"},"executionInfo":{"status":"ok","timestamp":1615934755754,"user_tz":420,"elapsed":326,"user":{"displayName":"Li Yin","photoUrl":"https://lh3.googleusercontent.com/a-/AOh14GgIRi0T9vdv7_5OZi96H4VGhtX2CMD9asUJHPo4cQ=s64","userId":"13365523799853678553"}},"outputId":"e169c2ed-a09a-435d-b141-7851747959dc"},"source":["floyd_warshall(W)"],"execution_count":173,"outputs":[{"output_type":"stream","text":["[[0, 2, 4, 7, -2], [inf, 0, 3, 8, -4], [inf, -2, 0, 6, -6], [inf, -5, -3, 0, -9], [inf, 5, 7, 13, 0]]\n"],"name":"stdout"},{"output_type":"execute_result","data":{"text/plain":["[[0, 2, 4, 7, -2],\n"," [inf, 0, 3, 8, -4],\n"," [inf, -2, 0, 6, -6],\n"," [inf, -5, -3, 0, -9],\n"," [inf, 5, 7, 13, 0]]"]},"metadata":{"tags":[]},"execution_count":173}]},{"cell_type":"markdown","metadata":{"id":"94WFec3HX6tn"},"source":["##Exercies\n","\n","1. 847. Shortest Path Visiting All Nodes (hard). Traveling salesman problem, but can be better with shortest path, breath-first, and dijkstra algorthm"]}]}